package algorithm.easy;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: Decode1720
 * @description: 未知 整数数组 arr 由 n 个非负整数组成。
 *
 * 经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。
 *
 * 给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。
 *
 * 请解码返回原数组 arr 。可以证明答案存在并且是唯一的。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：encoded = [1,2,3], first = 1
 * 输出：[1,0,2,1]
 * 解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/decode-xored-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/5/617:25
 * @since V1.0
 */
/**
 *根据题目给定的规则，利用如下异或性质从头做一遍即可：
 *
 * 相同数值异或，结果为 0
 * 任意数值与 0 进行异或，结果为数值本身
 * 异或本身满足交换律
 * 已知 encoded[i-1] = arr[i-1] XOR arr[i]，将等式两边同时「异或」上 arr[i-1]。可得：
 *
 * encoded[i-1] XOR arr[i-1] = arr[i-1] XOR arr[i] XOR arr[i-1]
 * 结合「性质三」和「性质一」，可化简「右式」得 encoded[i-1] XOR arr[i-1] = arr[i] XOR 0
 * 结合「性质二」，可化简「右式」得 encoded[i-1] XOR arr[i-1] = arr[i]
 *
 * 作者：AC_OIer
 * 链接：https://leetcode-cn.com/problems/decode-xored-array/solution/gong-shui-san-xie-li-yong-yi-huo-xing-zh-p1bi/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
//位运算符 异或运算
public class Decode1720 {
    public int[] decode(int[] encoded, int first) {
        int[] res = new int[encoded.length + 1];
        res[0] = first;
        for (int i=1;i<res.length;i++){
            //辅助计算公式:encoded[i-1] = res[i]^res[i-1];
            //辅助计算公式:encoded[i-1] ^ res[i-1] = res[i]^res[i-1] ^ res[i-1];
            //辅助计算公式:encoded[i-1] ^ res[i-1] = res[i]^0=res[i];
            res[i] = encoded[i-1] ^ res[i-1];
        }
        return res;
    }

}
